import java.util.*;

public class FindClosestElements {

    public List<Integer> findClosestElements1(int[] arr, int k, int x) {
        PriorityQueue<info> heap = new PriorityQueue<>(new Comparator<info>() {
            @Override
            public int compare(info a, info b) {
                int i = Math.abs(a.val - x);
                int j = Math.abs(b.val - x);
                if (i != j) {
                    return i - j;
                } else {
                    return a.index - b.index;
                }
            }
        });
        for (int i = 0; i < arr.length; i++) {
            heap.add(new info(i, arr[i]));
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ans.add(heap.poll().val);
        }
        ans.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        return ans;
    }

    public static void main(String[] args) {
        FindClosestElements findClosestElements = new FindClosestElements();
        int[] nums = {1,2,3,4,5};
        System.out.println(findClosestElements.findClosestElements(nums, 4, -1));
    }

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int l = 0;
        int r = arr.length - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] < x) {
                l = mid + 1;
            } else r = mid;
        }
        int p1 = l - 1, p2 = l;
        List<Integer> ans = new ArrayList<>();
        while (k-- > 0) {
            if (p1 < 0) {
                p2++;
            } else if (p2 >= arr.length) {
                p1--;
            } else if (arr[p2] - x >= x - arr[p1]) {
                p1--;
            } else p2++;
        }
        for (int i = p1 + 1; i < p2; i++) {
            ans.add(arr[i]);
        }
        return ans;
    }


    class info {
        public int index;
        public int val;

        public info(int index, int val) {
            this.index = index;
            this.val = val;
        }
    }
}

